Randomized algorithm
part 10/32 · 53.0 KB total
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Early works on hash tables either assumed access to a fully random hash function or assumed that the keys themselves were random.cite-ref-0-9-5[9] In 1979, Carter and Wegman introduced universal hash functions,cite-ref-12[12] which they showed could be used to implement chained hash tables with constant expected time per operation.
Early work on randomized data structures also extended beyond hash tables. In 1970, Burton Howard Bloom introduced an approximate-membership data structure known as the Bloom filter.cite-ref-13[13] In 1989, Raimund Seidel and Cecilia R. Aragon introduced a randomized balanced search tree known as the treap.cite-ref-14[14] In the same year, William Pugh introduced another randomized search tree known as the skip list.cite-ref-15[15]
Implicit uses in combinatorics